#include <queue>
#include <vector>
#include <iostream>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

struct compare {
    bool operator()(const ListNode* l1, const ListNode* l2) {
        return l1->val > l2->val;
    }
};

ListNode* mergeKLists(vector<ListNode*>& lists) {
    priority_queue<ListNode*, vector<ListNode*>, compare> q;

    for(auto list : lists) {
        if(list) {
            q.push(list);
        }
    }

    if(q.empty()) {
        return NULL;
    }

    ListNode* result = q.top();
    q.pop();

    if(result->next) {
        q.push(result->next);
    }

    ListNode* tail = result;            
    while(!q.empty()) {
        tail->next = q.top();
        q.pop();
        tail = tail->next;

        if(tail->next) {
            q.push(tail->next);
        }
    }

    return result;
}


int main() {
    // 创建链表 1->4->5
    ListNode* l1 = new ListNode(1);
    l1->next = new ListNode(4);
    l1->next->next = new ListNode(5);

    // 创建链表 1->3->4
    ListNode* l2 = new ListNode(1);
    l2->next = new ListNode(3);
    l2->next->next = new ListNode(4);

    // 创建链表 2->6
    ListNode* l3 = new ListNode(2);
    l3->next = new ListNode(6);

    // 将链表放入向量中
    vector<ListNode*> lists = {l1, l2, l3};

    // 合并链表
    ListNode* result = mergeKLists(lists);

    // 打印合并后的链表
    while(result != NULL) {
        cout << result->val << " ";
        result = result->next;
    }

    return 0;
}
